package leetcode_top;
import java.util.*;
import org.junit.*;

public class Ex146 {
    class LRUCache1 extends LinkedHashMap<Integer, Integer> {

        int capacity;
        public LRUCache1(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }
        
        public int get(int key) {
            return super.containsKey(key) ? super.get(key) : -1;
        }
        
        public void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
            return this.size() > this.capacity;
        }
    }

    /* 
    ["LRUCache","put","put","get","put","get","put","get","get","get"]
    [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
    */
    @Test
    public void test() {
        LRUCache lru = new LRUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        System.out.println(lru.get(1));
        lru.put(3, 3);
        System.out.println(lru.get(2));
        lru.put(4, 4);
        System.out.println(lru.get(1));
        System.out.println(lru.get(3));
        System.out.println(lru.get(4));

    }

    class LRUCache {

        Map<Integer, Node> map;
        DoubleList dl;
        int capacity;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>();
            dl = new DoubleList();
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                dl.removeNode(node);
                dl.addNode(node);
                return node.val;
            }
            return -1;
        }
        
        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                dl.removeNode(node);
                node.val = value;
                dl.addNode(node);
            } else {
                Node newNode = new Node(key, value);
                map.put(key, newNode);
                dl.addNode(newNode);
                if (map.size() > capacity) {
                    int k = dl.removeLast();
                    map.remove(k);
                }
            }

        }
    }

    class DoubleList {
        Node head, tail;

        public void addNode(Node node) {
            if (head == null && tail == null) {
                head = tail = node;
            } else /* if (head == tail)  */{
                node.next = head;
                head.prev = node;
                head = head.prev;
            }
        }

        public int removeLast() {
            int ret = tail.key;
            this.removeNode(tail);
            return ret;
        }

        public void removeNode(Node node) {
            if (node == head && node == tail) {
                head = tail = null;
            } else if (node == head) {
                head.next.prev = null;
                head = head.next;
            } else if (node == tail) {
                node.prev.next = null;
                tail = node.prev;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
        }
    }

    class Node {
        Node prev, next;
        int key, val;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    @Test
    public void test1() {
        int a, b;
        a = b = 1;
        a = b = 0;
        System.out.println(a);        
        System.out.println(b);
    }
}
